package middle;

public class Solution_134 {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] array = new int[gas.length << 1];


        for (int i = 0; i < gas.length; i++) {
            int sub = gas[i] - cost[i];
            array[i] = sub;
            array[gas.length + i] = sub;
        }
        int count = 0, index = -1;
        for (int i = 0; i < array.length; i++) {
            if (count > 0) {
                count += array[i];
            } else {
                count = array[i];
                index = i;
            }
        }
        System.out.println("count:"+count + "; index:"+index);
        if (index >= 0) {
            index %= gas.length;
            count = 0;
            for (int i = 0; i < gas.length; i++) {
                count += array[i + index];
                if (count < 0) {
                    return -1;
                }
            }
        }
        return index;
    }

    public static void main(String[] args) {
        Solution_134 model = new Solution_134();
        System.out.println(model.canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2}));
        System.out.println(model.canCompleteCircuit(new int[]{2, 3, 4}, new int[]{3, 4, 3}));
        System.out.println(model.canCompleteCircuit(new int[]{4}, new int[]{3}));
        System.out.println(model.canCompleteCircuit(new int[]{4}, new int[]{3}));
    }
}
